home *** CD-ROM | disk | FTP | other *** search
/ Mac Treasure Chest - Best Games 101 / 101.ISO / Strategy / GNU Chess 3.0 / DOCUMENTATION / MOVE-GEN < prev    next >
Encoding:
Text File  |  1992-01-27  |  3.2 KB  |  94 lines  |  [TEXT/MSWD]
  1. This file contains a description of GNU's new move generation algoritm.
  2.    Copyright (C) 1989 Free Software Foundation, Inc.
  3.  
  4. This file is part of CHESS.
  5.  
  6. CHESS is distributed in the hope that it will be useful,
  7. but WITHOUT ANY WARRANTY.  No author or distributor
  8. accepts responsibility to anyone for the consequences of using it
  9. or for whether it serves any particular purpose or works at all,
  10. unless he says so in writing.  Refer to the CHESS General Public
  11. License for full details.
  12.  
  13. Everyone is granted permission to copy, modify and redistribute
  14. CHESS, but only under the conditions described in the
  15. CHESS General Public License.   A copy of this license is
  16. supposed to have been given to you along with CHESS so you
  17. can know your rights and responsibilities.  It should be in a
  18. file named COPYING.  Among other things, the copyright notice
  19. and this notice must be preserved on all copies.
  20.  
  21. New move Generation algoritm:
  22.  
  23. Revision: 1989-09-06
  24.  
  25. Author: Hans Eric Sandstroem.
  26.  
  27. This algortim is the result of an attempt to make an hardware move
  28. generator, but since I newer had the time and resources to build
  29. the hardware I wrote a software version and incorporated that one
  30. into gnuchess. This was the best way I could think of sharing this
  31. algorithm with the computer chess community.
  32.  
  33. If there is anybody out there with the time and rescources to build
  34. a hardware move generator I will be glad to assist.
  35.  
  36. The general idea behind this algoritm is to pre calculate
  37. a lot of data. The data that is pre calculated is every possible move
  38. for every piece from every square disregarding any other pieces on the
  39. board. This pre calculated data is stored in an array that looks like
  40. this:
  41.  
  42. struct sqdata {
  43.   short nextpos;
  44.   short nextdir;
  45. };
  46. struct sqdata posdata[8][64][64];
  47. /* posdata[piecetype][fromsquare][destinationsquare] */
  48. example:
  49.     the first move for a queen at e8 is stored at;
  50.     posdata[queen][e8][e8].nextpos
  51.     suppose this is e7 and e7 is occupied then the next move
  52.     will be found in;
  53.     posdata[queen][e8][e7].nextdir
  54.  
  55. To handle the differeces between white and black pawns (they move in
  56. opposite directions) an array ptype has been introduced:
  57.  
  58. static const short ptype[2][8] = {
  59.   no_piece,pawn,knight,bishop,rook,queen,king,no_piece,
  60.   no_piece,bpawn,knight,bishop,rook,queen,king,no_piece};
  61.            ^^^^^
  62. And it is used like this:
  63.    piecetype = ptype[side][piece]
  64. When generating moves for pieces that are not black pawns, piece
  65. can be used directly in posdata. As in the example above.
  66.  
  67. Thus the only thing one has to do when generating the moves
  68. is to check for collisions with other pieces. 
  69. the move generation to do this looks like this: (for non pawns)
  70.     p = posdata[piece][sq];
  71.     u = p[sq].nextpos;
  72.     do {
  73.       if (color[u] == neutral) {
  74.     LinkMove(ply,sq,u,xside);
  75.     u = p[u].nextpos;
  76.       }
  77.       else {
  78.     if (color[u] == xside) LinkMove(ply,sq,u,xside);
  79.     u = p[u].nextdir;
  80.       }
  81.     } while (u != sq);
  82.  
  83.  - I`nt this just beautiful!
  84.  
  85. The array posdata is initialized in the routine Initialize_moves.
  86. This routine is called just once and it works so no time has been spent
  87. on the structure of this code. GenMoves and CaptureList generates the
  88. moves but the routines ataks, BRscan, Sqatakd, KingScan and trapped
  89. also relies on the move generation algoritm so they have also been
  90. rewritten.
  91.  
  92.  
  93.  
  94.